﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCodeSolutions
{
    /// <summary>
    /// 14.最长公共前缀
    /// </summary>
    class LeetCode14: LeetCodeBase
    {
        public override void Execute()
        {
            CommonFuntions.Print(LongestCommonPrefix(new string[] { "flower", "flow", "flight" }));
        }

        public string LongestCommonPrefix(string[] strs)
        {
            int strsLength = strs.Length;
            if (strsLength == 0 || strs[0] == "")
            {
                return "";
            }
            if (strsLength == 1)
            {
                return strs[0];
            }

            string commonPrefix = "";
            string shortestStr = "";
            /*for (int i = 0; i < strsLength - 1; i++)//找到最短单词
            {
                if(strs[i].Length < strs[i+1].Length)
                {
                    shortestStr = strs[i];
                }
            }*/

            List<string> strsList = strs.ToList();
            strsList.Sort(new CompareStr());
            shortestStr = strsList[0];
            for (int i = 0; i < shortestStr.Length; i++)
            {
                string compareStr = shortestStr.Substring(0, i + 1);
                if (strsList.TrueForAll((str) => { return str.StartsWith(compareStr); }))
                {
                    commonPrefix = compareStr;
                }
            }

            return commonPrefix;
        }

        public class CompareStr : Comparer<string>
        {
            public override int Compare(string x, string y)
            {
                return x.Length < y.Length ? 1 : 0;
            }
        }
    }
}
